1. Field of the Invention
The invention relates generally to a low density parity check (LDPC) decoder and more specifically relates to circuits to implement a parity unit in a parallel, pipelined, LDPC decoder.
2. Related Patents
This patent is related to commonly owned U.S. Ser. No. 11/565,670 entitled “Parallel LDPC Decoder” filed on 1 Dec. 2006 which is hereby incorporated by reference. This patent is also related to commonly owned U.S. Ser. No. 11/613,256 entitled “Low Complexity LDPC Encoding Algorithm” filed on 20 Dec. 2006 which is hereby incorporated by reference. This patent is related to commonly owned U.S. Ser. No. 11/626,400 entitled “Pipelined LDPC Arithmetic Unit” filed on 24 Jan. 2007 which is hereby incorporated by reference.
In digital channels, such as digital telecommunications and data storage read channels, error detection and correction is a key to the speed and reliability of the digital data exchanged. LDPC encoding and decoding is one of the best performing channel codes (encoding and decoding) known at present. It provides both robust error detection and correction and, with careful design, can provide high performance for error detection and correction at very high data rates.
In general, LDPC codes are linear block codes defined by a sparse matrix “H” called the parity check matrix. A column of H is associated with a codeword bit and each row corresponds to a parity check of codeword. A non-zero element in a row means that the corresponding column (e.g., bit of the codeword) contributes to this row's parity check.
Often an LDPC code is described by a so called “Tanner” graph in which a check node corresponds to each row of the parity check matrix and a bit node corresponds to each column of the parity check matrix. Edges connect a bit node to a check node if the column corresponding to the bit node contributes to the parity check of the row corresponding to the check node. This Tanner graph model is also suggestive of an architecture of an LDPC decoder in which bit nodes and check nodes exchange messages (e.g., log-likelihood or LLR messages) to converge through an iterative process on a determination of whether a codeword received on the digital channel is correct or is in error. The bit nodes provide an estimated value of a corresponding bit of a codeword and the check nodes compute a degree of certainty regarding the value of related bits. Through a series of iterations the LDPC decoder may converge on a level of certainty (correctness) or uncertainty (error) regarding any codeword received on the digital channel.
The Related Patents identified above describe aspects of a pipelined LDPC decoder that is well suited to parallel processing computations in the processing of each received codeword through the LDPC decoder of a digital channel. The circuits to provide such parallel computation of the LDPC decoder are complex. The Related Patents present an architecture with a plurality of bit nodes/units (“bit & memory logic”) and a plurality of check/parity nodes/units (“parity memory logic”) coupled through a bidirectional interleaver circuit (e.g., a programmable switch) all coupled to control logic (a controller) to sequence the computations and exchanges of messages between the bit nodes and the check nodes.
It is an ongoing challenge to design simpler circuits for the check nodes (parity units) that compute the parity using the parity check matrix (“H”) in such a parallel, pipelined LDPC decoder.